import functools
import heapq

class MedianFinder:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.little = []
        self.large = []
        self.littleKey = functools.cmp_to_key(lambda x,y:x-y)
        self.largeKey = functools.cmp_to_key(lambda x,y:y-x)

    def addNum(self, num):
        """
        Adds a num into the data structure.
        :type num: int
        :rtype: void
        """
        if not self.little:
            heapq.heappush(self.little, (self.littleKey(num), num))
            return
        

        if len(self.little)>len(self.large):
            if num<=self.little[0][1]:
                heapq.heappush(self.large, (self.largeKey(num), num))
            else:
                _, value = heapq.heapreplace(self.little, (self.littleKey(num), num))
                heapq.heappush(self.large, (self.largeKey(value), value))
        else:
            if num>=self.large[0][1]:
                heapq.heappush(self.little, (self.littleKey(num), num))
            else:
                _, value = heapq.heapreplace(self.large, (self.largeKey(num), num))
                heapq.heappush(self.little, (self.littleKey(value), value))


    def findMedian(self):
        """
        Returns the median of current data stream
        :rtype: float
        """
        if len(self.little)>len(self.large): return self.little[0][1]
        else: return (self.little[0][1]+self.large[0][1])/2.0

# Your MedianFinder object will be instantiated and called as such:
mf = MedianFinder()
for i in range(10):
    mf.addNum(1)
    print(mf.findMedian())